package std::collection;

import std::Object;

public class TreeMap : Map
{
	m_node->TreeMapNode;
	m_size->int=0;
	public TreeMap(){}
	public put(k->Object, v->Object)
	{
		if(k==null)return;
		node->TreeMapNode=m_node;
		if(node==null){
			m_node=new TreeMapNode(k,v);
			++m_size;
			return;
		}
		else{
			hashcode0->int=k.hashcode();
			while(true){
				hashcode1->int=node.k.hashcode();
				if(hashcode0<hashcode1){
					if(node.l==null){
						node.l=new TreeMapNode(k,v);
						++m_size;
						return;
					}
					else node=node.l;
				}
				else if(hashcode1<hashcode0){
					if(node.r==null){
						node.r=new TreeMapNode(k,v);
						++m_size;
						return;
					}
					else node=node.r;
				}
				else {
					node.k=k;
					node.v=v;
					return;
				}
			}
		}
	}
	public get(k->Object)->Object{
		if(k==null)return null;
		hashcode0->int=k.hashcode();
		node->TreeMapNode=m_node;
		while(node!=null){
			hashcode1->int=node.k.hashcode();
			if(hashcode0<hashcode1)node=node.l;
			else if(hashcode1<hashcode0)node=node.r;
			else return node.v;
		}
		return null;
	}
	public remove(k->Object)
	{
		if(k==null)return;
		hashcode0->int=k.hashcode();
		node->TreeMapNode=m_node;
		last->TreeMapNode=null;
		while(node!=null){
			hashcode1->int=node.k.hashcode();
			if(hashcode0<hashcode1){
				last=node;
				node=node.l;
			}
			else if(hashcode1<hashcode0){
				last=node;
				node=node.r;
			}
			else {
				if(last==null)m_node=null;
				else{
					if(last.l==node)last.l=null;
					else if(last.r==node)last.r=null;
				}
				--m_size;
				return;
			}
		}
	}
	public exist(k->Object)->boolean
	{
		if(k==null)return false;
		hashcode0->int=k.hashcode();
		node->TreeMapNode=m_node;
		while(node!=null){
			hashcode1->int=node.k.hashcode();
			if(hashcode0<hashcode1)node=node.l;
			else if(hashcode1<hashcode0)node=node.r;
			else return true;
		}
		return false;
	}
	public empty()->boolean{return m_size==0;}
	public clear(){m_node=null;m_size=0;}
	public size()->int{return m_size;}
	public keys()->Iterator{return new TreeMapIterator(m_node);}
	public values()->Iterator{return new TreeMapValueIterator(m_node);}
}

class TreeMapNode : Object
{
	public l->TreeMapNode;
	public r->TreeMapNode;
	public k->Object;
	public v->Object;
	public TreeMapNode(k->Object,v->Object){this.k=k;this.v=v;}
}

class TreeMapIterator : Iterator
{
	protected m_stack->Stack;
	public TreeMapIterator(node->TreeMapNode)
	{
		if(node==null)return;
		m_stack=new Stack();
		m_stack.push(node);
	}
	public hasNext()->boolean
	{
		if(m_stack==null)return false;
		return !m_stack.empty();
	}
	public next()->Object
	{
		if(m_stack==null)return null;
		if(m_stack.empty())return null;
		else{
			node->TreeMapNode=m_stack.pop();
			if(node.r!=null)m_stack.push(node.r);
			if(node.l!=null)m_stack.push(node.l);
			return node.k;
		}
	}
}

class TreeMapValueIterator : TreeMapIterator
{
	public TreeMapValueIterator(node->TreeMapNode){super(node);}
	public next()->Object
	{
		if(m_stack==null)return null;
		if(m_stack.empty())return null;
		else{
			node->TreeMapNode=m_stack.pop();
			if(node.r!=null)m_stack.push(node.r);
			if(node.l!=null)m_stack.push(node.l);
			return node.v;
		}
	}
}